package org.auto2;

import org.apache.commons.math3.ml.clustering.Cluster;
import org.apache.commons.math3.ml.clustering.DBSCANClusterer;
import org.apache.commons.math3.ml.clustering.DoublePoint;
import org.apache.commons.math3.ml.distance.DistanceMeasure;
import org.apache.commons.math3.ml.distance.EuclideanDistance;
import org.test.GPSPoint;
import org.test.GPSUtils;

import java.util.*;

/**
 * DBSCAN基于密度的聚类算法，将一组GIS经纬度坐标划分为若干个簇
 */
public class DBSCAN {

    private static final int SKIP = 5;

    /**
     * 将一组GPS点划分为若干个簇
     *
     * @param gpsPoints GPS点集合
     * @param eps       DBSCAN算法参数，两个点之间的最大距离
     * @param minPts    DBSCAN算法参数，簇中最小点的数量
     * @return 簇集合
     */
    public static List<Collection<GPSPoint>> clusterGPSPoints(List<GPSPoint> gpsPoints, double eps, int minPts) {
        List<DoublePoint> pointList = new ArrayList<>();
        Map<String, Object[]> dataMap = new HashMap<>();
        Map<Integer, GPSPoint> dataMap2 = new HashMap<>();

        int idx = 0;
        for (GPSPoint gpsPoint : gpsPoints) {
            GPSPoint xyPoint = GPSUtils.gps2xy(gpsPoint);
            DoublePoint doublePoint = new DoublePoint(new double[]{xyPoint.lng, xyPoint.lat});
            // 进行抽稀, 跳过一些点
            if (idx++ % SKIP == 0) {
                pointList.add(doublePoint);
            }
            // 全量数据进行索引(经纬度可能相同)
            dataMap.put(xyPoint.lng + "_" + xyPoint.lat, new Object[]{idx, gpsPoint});
            dataMap2.put(idx, gpsPoint);
        }

        DistanceMeasure measure = new EuclideanDistance();
        DBSCANClusterer<DoublePoint> clusterer = new DBSCANClusterer<>(eps, minPts, measure);
        List<Cluster<DoublePoint>> clusterList = clusterer.cluster(pointList);

        List<Collection<GPSPoint>> clusters = new ArrayList<>();
        for (Cluster<DoublePoint> cluster : clusterList) {
            Map<Integer, GPSPoint> treeMap = new TreeMap<>();
            for (DoublePoint dp : cluster.getPoints()) {
                double[] pt = dp.getPoint();
                Object[] vals = dataMap.get(pt[0] + "_" + pt[1]);
                // treeMap可以自动排序
                int index = (Integer) vals[0];
                treeMap.put(index, (GPSPoint) vals[1]);
                // 增加中间跳过的点
                for (int i = 1; i < SKIP; i++) {
                    GPSPoint gpsPoint = dataMap2.get(index + i);
                    treeMap.put(index + i, gpsPoint);
                }
            }
            Collection<GPSPoint> traces = treeMap.values();
            clusters.add(traces);
        }

        return clusters;
    }

}
